\documentclass[paper=a4, fontsize=11pt]{scrartcl}
\newcommand{\bfvec}[1]{\mbox{\boldmath$#1$}}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{calligra,chancery,charter}
\usepackage[top=0.75in, bottom=1in, left=0.5in, right=0.5in]{geometry} 
\usepackage{amsmath,amssymb}
\title{	
\normalfont \normalsize 
\textsc{Shanghai Jiaotong University, Zhiyuan College} \\ [25pt]
\huge Review\\
}
\author{Feng Shi}
\date{\normalsize\today}
\begin{document}
\maketitle
\section{Probability,Inequality}
\newpage
\section{Chapter 2}
\begin{enumerate}
\item[-] \textbf{Distance between points} $$|\bfvec{x}-\bfvec{y}|=
	\sqrt{\sum_{i=1}^d(x_i-y_i)^2}$$
\item[-] \textbf{Hypersphere}
\begin{enumerate}
\item[-] 
	\begin{align*}
	V(d)&=\int_{x_1=-1}^{x_1=1}\int_{x_2=-\sqrt{1-x_1^2}}^{x_2=\sqrt{1-x_2^2}}
	\cdots\int_{x_d=-\sqrt{1-x_1^2-x_2^2-\cdots-x_{d-1}^2}} dx_d\cdots dx_2dx_1\\
		&=\int_{S^d}\int_{r=0}^{r=1}r^{d-1}d\Omega dr
	\end{align*}
\item[-] 
	\begin{displaymath}
	A(d)=\frac{2\pi^{\frac{d}{2}}}{\Gamma(\frac{d}{2})}\quad 
	V(d)=\frac{\pi^{\frac{d}{2}}}{\Gamma(\frac{d}{2}+1)}=\left\{
	\begin{array}{ll} \frac{\pi^\frac{d}{2}}{(\frac{d}{2})!} & d \ even \\\\
		\frac{\pi^{\lfloor \frac{d}{2} \rfloor} 2^{\lceil \frac{d}{2} \rceil}}{d!!}
		& d \ odd
	\end{array} \right.
	\end{displaymath}
	$$V(r)=r^dV(d) \quad A(r)=r^{d-1}A(d)$$
\item[-] \textbf{Lemma 2.2 The volume is near the equator}\\
	$\forall c>0$, the fraction of volume of the hemisphere
	above the plane $x_1=\frac{c}{\sqrt{d-1}}$ is less than $\frac{2}{c}e^{-c^2/2}$\\
	As the equatorial slice grows fatter, the volume above and below it vanishes
	exponentially fast. \\
	The concentration of the volume is $O(\frac{r}{\sqrt{d}})$ around the equator.
\item[-] The volume is near a narrow annulus.
\item[-] \textbf{Lemma 2.3 The surface area is near the equator} \\
	Similar. The fraction falls off exponentially fast.
\end{enumerate} % end of sphere
\item[-] \textbf{Volumes of other solids} \\\\\\
\item[-] \textbf{High Dimensional Gaussian}
\begin{enumerate}
\item[-] $$p(x_i)=\frac{1}{\sqrt{2\pi}}e^{-\frac{x_i^2}{2}}$$
		$$p(\bfvec{x})=\frac{1}{(2\pi)^\frac{2}{d}}e^
	{-\frac{x_1^2+x_2^+\cdots+x_d^2}{2}}$$
\item[-] \textbf{Expected squared distance of a point} 
	Estimate $E(\bfvec{x}^2)
	=E(x_1^2+x_2^2+\cdots+x_d^2)=dE(x_1^2)\approx d\sigma^2$\\
	 Probability mass of a unit-variance Gaussian is $r^{d-1}e^{-r^2/2}$, which is
	 similar to calculating surface area since points of Gaussian concentrate in a 
	 thin annulus. Take derivative and set it $0$ gives $r=\sqrt{d-1}$.
\item[-] \textbf{Lemma 2.4} For a $d-$dimansional spherical Gaussian of variance 1,
	The fraction of mass outside $\sqrt{d-1}-c\leq r\leq \sqrt{d-1}+c$ is less than
	$\frac{4}{c^2}e^{-c^2/4}$.\\
	Also falls off exponentially fast.
\item[-] Distance between two random points on the sphere is $\sqrt{2d}\pm O(1)$
\item[-] When distance of the centers is $\delta=\Omega(d^{1/4})$ two Gaussian can
	be seperated directly.
\item[-] $\lbrace \bfvec{x}_1,\bfvec{x}_2...\bfvec{x}_n \rbrace$ is a set of n
	points in $d-$space, 
	$\bfvec{\mu}=\frac{1}{n}(\bfvec{x}_1+\bfvec{x}_2+\cdots\bfvec{x}_d)$
\item[-] \textbf{Lemma 2.6} The maximum likelihood spherical Gaussian for a set of 
	samples is the one with center equal to the center mean and variance eqaul the
	variance of the sample.
\end{enumerate} % end of gaussian
\item[-] \textbf{Random Projection and Johnson-Lindernstrauss Theorem}
\begin{enumerate}
\item[-] \textbf{Theorem 2.8 The Random Pojection Theorem} Projected length is about
	$\sqrt{\frac{k}{d}}$ proportional to the original length.\\
	$Prob(|\bfvec{w}|^2-\frac{k}{d}\geq\varepsilon \frac{k}{d} ) \leq 
	4e^{-\frac{k\varepsilon^2}{64}}$. The error also falls off exponentially fast.
\item[-] $k$ should be at least order $\ln n$.
\item[-] \textbf{Theorem 2.9 Johnson-Lindenstrauss Lamma} (gives a mutiplcative 
	factor bound) $$(1-\varepsilon)\frac{k}{d}|\bfvec{u-v}|^2
	\leq |f(\bfvec{u}-\bfvec{v})|^2 \leq (1+\varepsilon)\frac{k}{d}|\bfvec{u-v}|^2$$
	with probability at least $90\%$
\end{enumerate} % end of proj
\end{enumerate}% end of chp2
\newpage
\section{Chapter 3}
\begin{enumerate}
\item[-] Expected degree in $G(n,p=\frac{d}{n})$ is $d\frac{n-1}{n}\approx d$.\\
		The probability distribution of the degree of a vertex is binomial.
\item[-] \textbf{Theorem 3.1} 
	$$Prob(|np-deg(v)|\geq c^2\sqrt{np})\leq c_1max(e^{-c_2c^2},e^{-c_3c\sqrt{np}})$$
	Error falls of exponentially fast.
\item[-] \textbf{Corollary 3.2} if $p$ is $\Omega(\ln n /n\varepsilon^2)$,
	every vertex almost has degree $(1-\varepsilon)np$ to $(1+\varepsilon)np$.\\
	$\Omega$ is for the latter one in $max$.\\
	Proof: Use Poisson distribution to estimate binomial distribution.
\item[-] \textbf{Triangles} 
	$$E(x)=\binom{n}{3}(p)^3=\binom{n}{3}(\frac{d}{n})^3\approx \frac{d^3}{6}$$
	$$Prob(x=0)\leq \frac{Var(x)}{E^2(x)}\leq \frac{6}{d^3}+o(1)$$ \\
	Proof: Use indicator variable and square it. Only consider if two triangles
	intersect since we only square it. Square because $\sigma^2(x)=E(x^2)-E(x)^2$.
\item[-] \textbf{First \& Second Moment Method}
\begin{enumerate}
\item[-] \textbf{First Moment Method} $X$ is a nonnegative integer value random
	variable. Then $Prob(X>0)=Prob(X\geq 1)$. By Markov's inequality
	$Prob(X\geq 1)\leq E(x)$. \\
	When tsh expected value goes to zero, then a random graph almost surely has no
	occurrence of the item.
\item[-] \textbf{Second Moment Method} If $Var(X)=o[E^2(X)]$ then $X$ is almost surely
	greater than 0.\\
	Proof: By Chebyshev's inequality.
\item[-] \textbf{Corollary 3.4} $E(x)>0$. If $E(x)^2\leq E^2(x)(1+o(1))$ then $x$ is
	almost surely greater than 0.
\end{enumerate} % end of moment methods
\item[-] \textbf{Phase Transitions}
\begin{enumerate}
\item[-] \begin{tabular} {c | c}
	Property & Threshold \\
	\hline \\
	Cycles & $1/n$ \\
	Giant component & $1/n$ \\
	Giant component+Isolated vertices & $\ln n/2n$\\
	Connectivity,dissappearance of isolated vertices & $\ln n/n$ \\
	Diameter 2 & $\sqrt{2\ln n/n}$ \\
	Diameter $O(\ln n)$ & $c\ln n/n$
	\end{tabular}
\item[-]
\end{enumerate} % end of 3.2
\item[-] \textbf{Branching Process} 
\begin{enumerate}
\item[-] Generating function $f(x)=p_0+p_1x+p_2x^+\cdots$\\
		Next generation $f^2(x)$. Expected number of children $f'(1)$.
\item[-] \textbf{Lemma 3.10} Assume $f'(1)>1$, that is, the expected number of 
	children is greater than 1. Let $q$ be the unique root of $f(x)=x$ in $[0,1)$.
	$f_j(x)\to q$ as $j\to\infty$ for $x\in[0,1)$.
\item[-] \textbf{Theorem 3.11} $f(x)$ is the generating function of the number of
	children at each node.If $m=1$, probability of extinction is 0. If $m\leq 1$ and
	not always 1, probability of extinction is 1.
	If $m>1$, probability of extinction is the unique solution of $f(x)=x$ in [0,1).
\item[-] \textbf{Lemma 3.12}  If $m\neq 1$, the expected size of extinct family is
	finite. If $m=1$ and $p_1=1$,then it's a chain. If $m=1,p_1<1$ the expected size
	is infinite.
\end{enumerate} % end of braching
\item[-] \textbf{Monotone property}
\begin{enumerate}
\item[-] \textbf{Lemma 3.18} The probability of an increasing property being satified
	by $G(n,p)$	increases with $p$.
\item[-] \textbf{Theorem 3.19} Any monotone property $Q$ of $G(n,p)$ has a phase
	transition at $p_x$ where $x\in(0,1)$.
\end{enumerate} % end of monotone
\item[-]
\item[-]
\end{enumerate} % end of chp3
\newpage
\section{Chapter 4}
\begin{enumerate}
\item[-] Purpose: to get matrix of any rank that best approximates the original one.
\item[-] 
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\end{enumerate} % end of chp4
\newpage
\section{Chapter 5}
\begin{enumerate}
\item[-] A walk can start with any probability distribution \bfvec{p}.
	\bfvec{p} is a row vector with \emph{nonnegative} components \emph{summing to 1},
	with $p_x$ being theprobability of starting at vertex $x$.
\item[-] The probability of being at vertex $x$ at time $t+1$
\item[-] $\bfvec{p}^{(t)}$ is a row vetor with a component for each vertex specifying
	the \emph{probability mass} of the vertex at time $t$. That shows the liklyhood
	of the walk being at the vertex.
	(using probability mass only avoid the requirement of the components summing to 1)
	$$\bfvec{p}^{(t)}=\bfvec{p}^{(t-1)}\bfvec{P}$$
	where \bfvec{P} gives transition probability of adjacent vertices.
\item[-] \textbf{Long-term probability} 
	$$\bfvec{a}^{(t)}=\frac{1}{t}\sum_{i=0}^t-1\bfvec{p}^{i}$$
	(Multiplying $t$) 
	gives the probability of each vertex appearing in the first t steps of the walk.
\item[-] \textbf{Stationary probability} $\bfvec{\pi}$ is also a row vector.
\item[-] \textbf{Lemma 5.1} \textsl{$\bfvec{A}=[\bfvec{P-I},\bfvec{1}]$ has rank n.}\\
	Proof: Consider $\bfvec{A}\binom{\bfvec{x}}{\bfvec{y}}=\bfvec{0}$.
	Since each row of \bfvec{P} sums to 1, $\binom{\bfvec{1}}{\bfvec{0}}$ 
	is a solution. If there is another solution, it togather with 
	$\binom{\bfvec{1}}{\bfvec{0}}$ span a space perpendicular to \bfvec{A}, thus there
	is a solution that is perpendicular to $\binom{\bfvec{1}}{\bfvec{0}}$, 
	say $\binom{\bfvec{w}}{\alpha\bfvec{1}}$ where \bfvec{w} is nonzero vector.
	$\bfvec{(P-I)w}+\alpha\bfvec{1}=\bfvec{0}$.
	$\bfvec{w}_i=\sum_{j}p_{ij}\bfvec{w}_j+\alpha$ so $\bfvec{w}_i$ is a 
	convex combination of $\bfvec{w}_j$ (plus constant). 
	From the formula 
	$$\bigg(\bfvec{P-I} \ \bfvec{1}\bigg)\binom{\bfvec{w}}{\alpha\bfvec{1}}=\bfvec{0}
	$$ we have $\sum_{j}\bfvec{w}_j=0$. So components of \bfvec{w} are not all equal.
	Rest of the proof uses symmetric arguments about $\alpha$.
\item[-] \textbf{Theorem 5.2 (Fundamental Theorem of Markov Chains)}\\\textsl{
	If the Markov chain is connected, there is a unique probability vector $\pi$ 
	satisfying $\pi\bfvec{P}=\pi$. For any starting distribution, 
	$lim_{t\to\infty}\bfvec{a}^{(t)}=\pi$.}\\
	If the underlying graph is strongly connected then the long-term average 
	probabilities approaches stationary probabilities.\\
	Proof:First consider \bfvec{A}. By lemma 5.1 \bfvec{A} is rank $n$, so there is a
	unique solution to $\bfvec{A}\binom{\bfvec{x}}{\bfvec{y}}=\bfvec{0}$ and that
	solution $\binom{\bfvec{1}}{\bfvec{0}}$ implies eliminating the last column of 
	\bfvec{A} makes the first $n$ columns linearly dependent and that's the only way
	of doing it. Thus \emph{removing any column of \bfvec{A} but the last one 
	results in a $n\times n$ submatrix of \bfvec{A} of rank $n$}.
\item[-] \textbf{Lemma 5.2 (Return time)} $r_x=\frac{1}{\pi _x}$\\
		Consider independent returnings and $ta_x^{(t)}$.
\item[-] Relationship between random walk and electrical network:
	$p_{xy}=\frac{c_{xy}}{c_x}$
\item[-] \textbf{Lemma 5.4} \textsl{For a random walk on a strongly connected graph,
	if vector \bfvec{u} has $u_xp_{xy}=u_yp_{yx}$ then \bfvec{u} is the stationary
	distribution of the walk}. (Consider \emph{traffic} between $x$ and $y$)\\
	$\pi _x=\frac{c_x}{c_0}$ where $c_0=\sum_{y}c_y$. They similarly shows the 
\item[-] \textbf{Harmonic function} $f_x=\sum_{y}f_yp_{xy}$
\item[-] A harmonic function on a connected graph takes maximum and minimum on the 
	boundary.
\item[-] There is at most one harmonic function satisfying a given set of equations
	and boundary conditions.\\ Boundary conditions determine a harmonic function.
\item[-] \textbf{Analogy between electrical network and random walk}
	\begin{enumerate}
	\item[-] \textbf{Probabilistic interpretation of voltages}
	Having fixed the voltages at the vertices $a$ and $b$, the voltage at an
	arbitary vertex $x$ equals the probability of a random walk starting at $x$
	reaching a before reaching b.
	\item[-] \textbf{Probabilistic interpretation of current}
	If the voltage $v_a$ is adjusted so that the current flowing into $a$ is
	1, then the current flowing through an edge is the net frequency with which a 
	random walk from $a$ to $b$ traverses the edge.\\
	Proof Sketch: Consider $u_x$ the expected number of visits of $x$ in the walk from
	$a$ to $b$ before reaching $b$. \\
	$u_x=\sum_{y\neq b}u_yp_{yx}$ and $u_yp_yx$ is the expected number of times the
	edge $xy$ is traversed from $y$ to $x$.
	\item[-] \textbf{Effective Resistance and Escape Probability}\\
		$P_{escape}=\frac{c_{eff}}{c_a}$ , $c_{eff}=\frac{i_a}{v_a}$\\
	Escape probability is the probability that a random walk starting at $a$ reaches
	$b$ before returing to $a$.\\
	Proof Sketch: $i_a=\sum_{y}(v_a-v_y)c_{ay}$ is the traffic at $a$\\
	$\sum_{y}p_{ay}v_y$ is the probability of a walk starting at $a$ 
	(to any direction) returning to $a$ before reaching $b$.
	\item[-] For a finite connected graph the escape probability is nonzero.
	\item[-] Merging all vertices at distance $d$ of greater from $a$ into one and 
	let it be the end point $b$. Let $d$ ``expand'', consider the limitation of 
	$p_{escape}$.
	\end{enumerate}
\item[-] \textbf{Random Walks on Undirected Graphs with Unit Edge Weights}
\begin{enumerate}
\item[-] \textbf{Lemma 5.5} The expected time for a random walk to pass a path of 
	$n$ vertices if $\Theta(n^2)$.\\
	Proof: Consider hitting time of adjacent vertices and add them up along the path.
\item[-] \textbf{Lemma 5.6}
	Consider a random walk from $1$ to $x$ in a chain with $n$ vertices. The expected
	time spent at vertex $i$
\item[-] Adding edges may either increase or decrease $h_{hy}$.\\
		Consider a chain, a clique with half of the vertices with a tail, a full
		clique. \\
		Hitting time is not symmetric: consider a clique with a tail.
\item[-] \textbf{Commute time} Start at $x$, hit $y$ and return.
\item[-] \textbf{Theorem 5.7} Given a undirected graph with edge replaced by 1 ohm.
	The commute time $com(x,y)=h_{xy}+h_{yx}=2mr_{xy}$ where $r_{xy}$ is 
	effective resistance, m is total number of edges.\\
	Proof: Since all edges are 1 ohm resistors, sum of currents out of some vertex is
	the degree of it. \\
	$h_{ij}=\sum_{k adj to i}\frac{1}{d_i} (1+h_{kj})$.\\
	When inserting currents to every vertex with their degrees, $h_{ij}=v_{ij}$.\\
	Insert current to all vertices and extract from one,$h_{ij}=v_{ij}$, get setup 1.\\ 
	Extract from another vertex, $h_{ji}=v_{ji}$, get setup 2.\\
	Reverse currents in setup 2,$h_{ji}=-v_{ji}$ get setup 2'. $h_{ij}=v_{ji}$
	\\\\???
	\\???\\\\
	Mix 1 and 2', there is only in-current to one vertex and out-current from one
	and the total traffic is 2m.
\item[-] \textbf{Corollary 5.8}
	If $x$ and $y$ are connected by and edge the $h_{xy}+h_{yx}=com(x,y)\leq 2m$
\item[-] \textbf{Corollary 5.9} $com(x,y)\leq n^3$\\
		Proof: Estimate $m$ and estimate $r_{eff}$.
\item[-] \textbf{Cover time} $cover(x,G)$ is the \emph{expected} time of $G$ coverd
	from $x$. $cover(G)=max_{x} cover(x,G)$.
\item[-] \textbf{Theorem 5.10} $G$ be a connected graph with $n$ vertices and $m$ 
	edges. $cover(G)\leq 2m(n-1)$.\\
	Proof: Consider a DFS and edges between vertices that are adjacent on the DFS 
	tree. Each edge on the DFS tree is traversed twice in each direction.
\item[-] \textbf{Theorem 5.11} $G$ be a undirected graph with $m$ edges.
	Redefine $r_{eff}=max r_{xy}$
	$$mr_{eff}\leq cover(G) \leq 2e^3 mr_{eff}\ln{n}+n$$\\
	Proof: 
\end{enumerate} %end of 5.3
\item[-] \textbf{Random Walks in Euclidean Space} 
\begin{enumerate}
\item[-] Assume resistors are 1 ohm. For
	$d-$dimensional lattice, $p_{escape}=\frac{1}{2dr_{eff}}$.
\item[-] \textbf{Two dimensions} $r_{eff}\geq \Theta(\ln n)$
\item[-] \textbf{Three dimensions} $\frac{1}{6}\leq p_{escape}\leq \frac{5}{6}$
\end{enumerate} % end of 5.4
\item[-] \textbf{Web as a Markov Chain}\\
	Add restart probability to ensure strong connectedness.
\begin{enumerate}
\item[-] \textbf{Page Rank} Equals the stationary probability.
	Adding short loops thus reducing return time increases page rank.
\item[-] \textbf{Spam} Methods to increase page rank: Delete out edges and add loop, 
	create a star.\\
	More or less frequent random restarts.
\item[-] \textbf{Hitting time}
\end{enumerate} % end of 5.5
\item[-] \textbf{Markov Chain Monte Carlo}
\begin{enumerate}
\item[-] The problem of estimating volumes is reducible to the problem of drawing 
	uniform random samples. A way to solve this is put a grid on the region and do
	a randomo walk on the grid points. The number of points is exponential in $d$. 
	Markov Chain leads to a polynomial time algorithm for a bounded convex region.
\item[-] We estimate $E(f)=\sum_{i}f_ip_i$ ($i$ is a state) with the average value 
	of $f$ at the states seen in a $t$ step run. Call this estimate $a$.
	$$E(a)=\sum_{i}f_i(\frac{1}{t}\sum_{m=1}^tProb(\mbox{walk is in state i at time t}))
	=\sum_{i}f_ia_i$$
\item[-] \textbf{Proposition 5.12} For 2 probability ditribution \bfvec{p} and 
	\bfvec{q}, \\\\\\\\\\\\\\\\\\\\\\\
\end{enumerate} % end of 5.6
\end{enumerate}%end of chapter 2
\newpage
\section{Chapter 6}
\begin{enumerate}
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\item[-]
\end{enumerate} % end of chp6
\newpage
\section{Chapter 7}
\end{document}

